﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    /*
    1237. 找出给定方程的正整数解
    中等
    86
    相关企业
    给你一个函数  f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。

    尽管函数的具体式子未知，但它是单调递增函数，也就是说：

    f(x, y) < f(x + 1, y)
    f(x, y) < f(x, y + 1)
    函数接口定义如下：

    interface CustomFunction {
    public:
      // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
      int f(int x, int y);
    };
    你的解决方案将按如下规则进行评判：

    判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
    判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
    判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
    如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。
 

    示例 1：

    输入：function_id = 1, z = 5
    输出：[[1,4],[2,3],[3,2],[4,1]]
    解释：function_id = 1 暗含的函数式子为 f(x, y) = x + y
    以下 x 和 y 满足 f(x, y) 等于 5：
    x=1, y=4 -> f(1, 4) = 1 + 4 = 5
    x=2, y=3 -> f(2, 3) = 2 + 3 = 5
    x=3, y=2 -> f(3, 2) = 3 + 2 = 5
    x=4, y=1 -> f(4, 1) = 4 + 1 = 5
    示例 2：

    输入：function_id = 2, z = 5
    输出：[[1,5],[5,1]]
    解释：function_id = 2 暗含的函数式子为 f(x, y) = x * y
    以下 x 和 y 满足 f(x, y) 等于 5：
    x=1, y=5 -> f(1, 5) = 1 * 5 = 5
    x=5, y=1 -> f(5, 1) = 5 * 1 = 5
 

    提示：

    1 <= function_id <= 9
    1 <= z <= 100
    题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
    在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。
     */
    public class Solution1237
    {
        public interface CustomFunction
        {
            // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
            int f(int x, int y);
        };
        /// <summary>
        /// 平平无奇的遍历方法
        /// </summary>
        /// <param name="customFunction"></param>
        /// <param name="z"></param>
        /// <returns></returns>
        public IList<IList<int>> FindSolution(CustomFunction customFunction, int z)
        {
            var result = new List<IList<int>>();
            for (int x = 1; x <= 1000; x++)
            {
                for (int y = 1; y <= 1000; y++)
                {
                    if (customFunction.f(x, y) == z)
                    {
                        result.Add(new List<int>(new[] { x, y }));
                    }
                }
            }
            return result;
        }
        /// <summary>
        /// 第二个方法利用给定函数严格单调的特点，检查行或者列，
        /// 如果z不在某行或某列的第一个和最后一个值的范围内，则该行或该列肯定没有解;
        /// 或者z刚好等于第一个或最后一个，则该行或列上，正是唯一解(严格单调性)
        /// 否则利用某行或某列有序(严格单调)的特点进行二分法查找
        /// </summary>
        /// <param name="customfunction"></param>
        /// <param name="z"></param>
        /// <returns></returns>
        public IList<IList<int>> FindSolution2(CustomFunction customfunction, int z)
        {
            var result = new List<IList<int>>();
            for (int x = 1; x <= 1000; x++)
            {
                var headVal = customfunction.f(x, 1);
                var tailVal = customfunction.f(x, 1000);

                int y = BinaryFind(customfunction, x, 1, 1000, z);
                if (y == -1 || y == -2)
                {
                    continue;
                }
                else if (y > 0)
                {
                    result.Add(new List<int>(new[] { x, y }));
                }
            }
            return result;
        }
        /// <summary>
        /// 二分法查找
        /// </summary>
        /// <param name="customfunction"></param>
        /// <param name="x"></param>
        /// <param name="yStart"></param>
        /// <param name="yEnd"></param>
        /// <returns>如果满足给定z的y值解小于yStart,返回-1，如果大于yEnd返回-2，如果z处于范围内，但没有解存在，返回-3，否则返回满足的y值</returns>
        private int BinaryFind(CustomFunction customfunction, int x, int yStart, int yEnd, int z)
        {
            var z_yStart = customfunction.f(x, yStart);
            var z_yEnd = customfunction.f(x, yEnd);
            if (z < z_yStart)
            {
                return -1;
            }
            if (z > z_yEnd)
            {
                return -2;
            }
            if (z_yStart == z)
            {
                return yStart;
            }
            if (z_yEnd == z)
            {
                return yEnd;
            }
            var yMiddle = (yStart + yEnd) / 2;
            if (yStart == yMiddle)
            {
                return -3;
            }
            else
            {
                var zMiddle = customfunction.f(x, yMiddle);
                if (zMiddle > z)
                {
                    return BinaryFind(customfunction, x, yStart, yMiddle, z);
                }
                else
                {
                    return BinaryFind(customfunction, x, yMiddle, yEnd, z);
                }
            }
        }
    }
}
